package demo04ArrayListLinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 14
 * Time:16:11
 */

/***
 *  线性表：顺序表和链表都属于线性表；
 *  树、图不是线性表；
 * 一、顺序表ArrayList 和LinkedList的区别
 * 1.ArrayList
 * Java中的ArrayList是以1.5倍进行扩容的；
 *   缺点：
 *    (1)一般情况下：在插入/删除元素的时候，时间复杂度最坏是O(n);
 *
 *  优点：
 *   （1）顺序表的底层是数组（空间连续，支持随机访问），如果是通过下标直接取数据，时间复杂度可以达到O(1)
 *
 * 2.LinkedList
 * 链表的优点：（1）任意位置插入删除节点的时间复杂度是O(1);
 *            (2)没有增容问题，插入一个开辟一个空间；
 *      缺点：以节点为存储单位，不支持随机访问；
 *
 * 定义：
 * （1）data——代表数值域；
 * （2）next——引用，存放下一个节点的指针；
 *
 *   head——头结点；
 *  单链表：第一个节点是头结点，最后一个节点是尾结点；
 *
 * 3.查看内存泄漏命令:
 * (1)jps;
 * (2) jmap -histo:live 进程号 > d:f.txt
 *
 * 4.常用JDK命令：
 * （1）java
 * （2）javac
 * （3）jps——查看进程号
 * （4）jmap——查看内存泄漏情况
 *
 * 5.
 */
class  Node{
    public int val;//数值域
    public Node next;//引用，保存下一个节点的指针

    public Node(){

    }

    public Node(int val){
        this.val = val;
    }

}
public class MyLinkedList {

    public Node head;//表示当前链表的头，是一个引用,默认值是null

    /***
     * 创建单链表
     */
    public void createLinked(){
        this.head = new Node(22);
        Node node2 = new Node(23);
        Node node3 = new Node(34);
        Node node4 = new Node(42);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
    }

    /***
     * 1.打印链表
     */
    public void display1(){
        Node cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /***
     * 从指定节点开始打印链表
     */
    public void display2(Node newHead){
        Node cur = newHead;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /***
     * 2.通过遍历，找到链表的最后一个节点
     * @return 返回最后一个节点的引用
     */
    public Node findLastNode(){
        if(this.head == null){
            System.out.println("head == null");
            return  null;
        }
        Node cur = this.head;
        while(cur.next != null){
            cur = cur.next;
        }
        return cur;
    }

    /***
     * 3.通过遍历，找到链表中的倒数第二个节点
     * 考虑情况1：一个节点也没有；
     * 考虑情况2：只有一个节点
     * cur.next.next == null
     * @return
     */
    public Node findLastTwo(){
        //考虑一个节点没有
        if(this.head == null){
            System.out.println("一个节点也没有！");
            return  null;
        }
        //考虑只有一个节点的情况
        if(this.head.next == null){
            System.out.println("当前链表只有一个节点！");
            return null;
        }
        Node cur = this.head;
        while(cur.next.next != null){
            cur = cur.next;
        }
        return cur;
    }

    /***
     * 4.查找第n个节点
     * @return
     */
    public  Node findNnode(int n ){
        //(1)单链表为空
        if(head == null){
            System.out.println("单链表为空！");
            return  null;
        }
        //（2）n不合法，小于等于0
        if(n <= 0){
            System.out.println("n 小于等于0！");
            return null;
        }
        //(3)n大于链表的长度
        if(n > len()){
            System.out.println("n大于链表的长度！");
            return  null;
        }
        int count = 1;
        Node cur = this.head;
        while(count != n){
            cur = cur.next;
            count ++;
        }
        return cur;
    }

    /***
     * 5.求单链表的长度
     * @return
     */
    public int len(){
        Node cur = this.head;
        int count = 0;
        while(cur != null){
            count++;
            cur  = cur.next;
        }
        return count;
    }

    /*****
     * 6.查找单链表中是否包含关键字 key
     * @param key
     * @return
     */
    public boolean contains(int key){
        Node cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return  false;
    }
    /***
     * 1.头插法
     * @param data
     */
    public Node addFirst(int data){
/*        //（0）创建节点
        Node node = new Node(data);
        //(1)判断链表是否为为空
        if(this.head == null){
            this.head = new Node(data);
        }else{
            //(2)插入数据
            node.next = this.head;
            this.head = node;
        }
        return head;*/

        //优化：
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;
        return head;
    }

    /***
     * 2.尾插法
     * @param data
     * @return
     */
    public boolean addLast(int data){
        //(0)创建节点
        Node node = new Node(data);
        //定义cur,找到节点的尾巴
        Node cur = this.head;
        if(this.head == null){
            this.head = node;
        }else{
            //(1)找到节点的尾部
            while(cur.next != null ){
                cur = cur.next;
            }
            //（2）插入数据
            cur.next = node;
        }
        return  false;
    }

    /***
     * 3.任意位置插入，第一个数据节点为0号下标
     *
     * @param index
     * @param data
     */
    public void addIndex(int index,int data){
        if(index < 0 || index > len()){
            System.out.println("index不合法！");
            return;
        }
        if(index == 0){//头插法
            addFirst(data);
            return;
        }
        if(index == len()){//尾插法
            addLast(data);
            return;
        }
        Node cur = findIndex(index);//cur保存的是index - 1位置的节点的引用
        Node node = new Node(data);
        //先绑定后边，在连接前面
        node.next = cur.next;
        cur.next = node;
    }

    /***
     * 该函数是找到index - 1位置的节点的引用
     * @param index
     * @return
     */
    public Node findIndex(int index){
        Node cur = this.head;
        int count = 0;
        while(count != index - 1){
            cur = cur.next;
            count++;
        }
        return cur;
    }

    /***
     * 4.删除第一次出现关键字key节点
     * (1)找到待删除节点的前驱；
     * (2)链表中是否存在该节点；
     * (3)关键字key出现在头结点；
     * (4)链表为空
     * @param key
     */
    public void delete(int key){
        //(1)链表为空
        if(this.head == null){
            return;
        }
        //（2）关键字key出现在头结点
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        //(3)其它情况：正常的进行删除
        Node ret = findPrev(key);
        if(ret == null){//没有此前驱
            System.out.println("删除失败，因为没有待删除key节点的前驱！");
        }else{//找到了待删除节点的前驱
/*            Node del = ret.next;
            ret.next = del.next;*/
            ret.next = ret.next.next;
        }
    }

    /***
     * 找到关键字key的前驱
     * 如果有，则返回前驱节点的引用;
     * 如果没有，则返回null
     * @param key
     * @return
     */
    public Node findPrev(int key){
        Node cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return  cur;
            }
            cur = cur.next;
        }
        return null;//代表没有要删除的key值的前驱
    }

    /**
     * 5.删除所有值为key的节点
     * 在删除结束之后：对头结点进行判断，看头结点是否是待删除的节点
     * @param key
     */
    public Node deleteAllKey(int key){

        if(head == null){
            return null;
        }
        Node prev = this.head;
        Node cur = prev.next;//cur代表要删除的节点
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            this.head = this.head.next;
        }
        return head;

    }

    /***
     * 6.清空链表
     */
    public void clear(){
        this.head = null;
    }

    /***
     * 7.反转一个单链表
     * （1）定义一个前驱prev = null;
     * （2）定义待反转的节点cur
     * （3）定义把保存下一个待反转的节点curNext
     */

    public Node reverse1(){
        if(this.head == null){
            System.out.println("链表为空！");
            return null;
        }
        //定义一个前驱prev = null;
        Node prev = null;
        //定义待反转节点cur
        Node cur = this.head;
        while(cur != null){
            //定义保存下一个节点的curNext
            Node curNext = cur.next;
            cur.next  = prev;
            prev = cur;
            cur = curNext;
        }

        return prev;
    }

    /***
     * 反转链表方法2：
     * （1）定义一个前驱节点prev = null;
     * （2）定义一个新的头结点newHead;
     * （3）定义一个待反转节点cur;
     * @param head
     * @return
     */
/*    public Node  reverse2(){
        //定义一个前驱节点
        Node prev = null;
        //定义链表的新头节点
        Node newHead = null;
        //定义待反转节点cur
        Node cur = this.head;
        while(cur != null){
            //保存待反转节点的下一个节点
            Node curNext = cur.next;
            if(curNext == null){
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }*/

    /**
     * 反转链表3：使用头插法实现链表的反转
     *
     * @return
     */
    public Node reverse3(){
        //定义待反转节点cur
        Node cur = this.head;
        Node newHead = null;
        while(cur != null){
            //保存待反转节点的下一个节点
            Node curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        return newHead;
    }

    /***
     * 8.找链表的中间节点
     * 给定一个头结点为head的非空单链表，返回链表的中间节点；
     * 如果有两个中间节点，则返回第二个中间节点；
     * @param head
     * @return
     */
    //  定义快慢指针查找中间节点
    public Node middleNode1(Node head){
        Node fast = this.head;
        Node slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //方法2:求得链表的长度len / 2 ，即可以找到链表的中间节点；
    public Node middleNode2(Node head) {
    //求链表的长度
        int len = len() / 2;
        Node cur = this.head;
        int count = 0;
        while(count != len){
            cur = cur.next;
            count++;
        }
        return cur;
    }

    /***
     * 9.找到链表的倒数第k个节点
     * (1)先让fast 走k步;
     * (2)然后fast和slow一起往后走；当fast.next == null 的时候；
     * （3)返回slow：就是倒数第k个节点
     * @param k
     * @return
     */
    public Node findKthToTail1(int k){
        //（1）考虑链表为空
        //（2）以及k  < 0
        //（3）K > 链表的长度——可导致空指针异常
        if(head == null || k <= 0){
            return  null;
        }
        Node fast = this.head;
        Node slow = this.head;
        //（1）先让你fast走k - 1 步；
        while(k - 1 != 0){
            //每次走之前，判断肚囊谦fast是不是走到了尾巴节点
            if(fast.next != null){//在此处进行判断k值是否大于链表的长度
                fast = fast.next;
                k--;
            }else{
                return null;//代表k的值大于链表的长度
            }
        }
        //（2）接下来，fast 、slow一起往后走；
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        //(3)当fast.next == null 的时候，此时slow指向的节点就是倒数第k个节点
        return slow;
    }

/*    *//***
     * 查找倒数第k个节点
     * 求的链表的长度；然后定义cur 走len - k，即可以得到倒数第k个节点
     * @param k
     * @return
     *//*
    public Node findKthToTail2(int k) {
        if(this.head == null || k < 0 ||  k > len()){
            return null;
        }
        //(1）求得链表的长度
        int len = len();
        Node cur= this.head;
        //(2)定义cur 需要走的步数count
        int count = len - k;
        while(count != 0){
            cur = cur.next;
        }
        return  cur;
    }*/

    /**
     * 10.合并两个有序单链表
     * @param headA
     * @param headB
     */
    public Node merge(Node headA,Node headB){
        //创建一个虚拟节点
        Node prev = new Node(-1);
        //创建一个节点tmp：用于返回合并之后的新链表的头：tmp.next
        Node tmp = prev;
        //(1)当headA 和 headB 都为空；
        if(headA == null && headB == null){
            return null;
        }
        //(2)当headA 和headB 都不为空的时候

        while(headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }
            else{
                tmp.next = headB;

                tmp = tmp.next;
            }
        }
        //代码走到此处
        //如果headA为空，直接拼接headB即可
        if(headA != null){
            tmp.next = headA;
        }
        if(headB!= null){
            tmp.next = headB;
        }
        return prev.next;
    }

    /***
     * 11.以给定值x为基准将链表分成两个部分，
     * 所有小于x的节点排在大于或者等于x节点之前
     * 解法：定义两段，比x存储在第一段，比x大的存储在第二段
     * 最后将两段进行拼接即可
     * @param x
     * @return
     */
    public Node partition(int x){
        if(this.head == null){
            return  null;
        }
        //定义第一段：存储比小于x节点值的部分；
        Node bstart = null;
        Node bend = null;
        //定义第二段：存储大于x节点值的部分
        Node astart = null;
        Node aend = null;

        Node cur = this.head;
        while(cur != null){

            if(cur.val < x){
                //第一段：
                if(bstart == null){
                    //第一段：第一次插入节点，
                    bstart = cur;
                    bend = cur;
                }else{
                    //第一段：已经有了节点
                    bend.next = cur;
                    bend = bend.next;
                }

            }else {
                //第二段：
                if(astart == null){
                    //第二段：第一次插入节点：
                    astart = cur;
                    aend = cur;
                }else{
                    //第二段：已经有了插入的节点
                    aend.next = cur;
                    aend = aend.next;
                }
            }
            cur = cur.next;
        }

        if(bstart == null){
            //说明第一段没有数据
            return  astart;
        }
        //将两段进行拼接
        aend.next = astart;
        //手动将链表的最后置空
        if(astart != null){
            //说明第二段不为空，手动将第二段置空
            aend = null;
        }
        return bstart;

    }


    /***
     * 12.在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，
     *   重复的节点不保留，返回链表头指针；
     * @return
     */
    public Node deleteDuplication(){
        if(head == null){
            return  null;
        }
        Node cur = this.head;
        Node newHead = new Node(-1);
        Node tmp = newHead;
        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
            }else{
                tmp.next = cur;
                cur = cur.next;
                tmp = tmp.next;
            }
        }
        //手动将末尾置空
        tmp.next = null;
        return  newHead.next;
    }

    /****
     * 13.链表的回文结构
     *    1 2 3 2 1
     *    找到链表的中间位置（定义fast、slow），将后半部分进行逆置；
     *    如果前面部分和后面部分相同——则就是回文结构
     * @return
     */
    public boolean isHuiwen(){
        if(this.head == null){
            return  false;
        }
        //（1）找链表的中间节点位置
        Node fast= this.head;
        Node slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        Node cur = slow.next;//待反转节点
        //(2)从中间位置开始，将后半部分【slow fast】部分进行反转
        while(cur != null){
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //(3)判断前后两部分的对应的val值是否相等：head从前往后走，slow从后往前走
        while (head != slow){
            if(head.val != slow.val){
                return  false;
            }
            //判断偶数的情况
            if(head.next == slow){
                return  true;
            }
            head = head.next;
            slow = slow.next;

        }
        return true;
    }

    /***
     * 14.输入两个链表，找出它们的第一个公共节点
     * 是Y型相交
     * 方式1：首先遍历链表得到链表的长度，让长的链表先走若干步，接着同时在两个链表上进行遍历，找到的第一个相同的节点就是它们的第一个公共节点；
     * 方法2：使用栈实现：分别将两个链表的节点放入两个栈中，这样两个链表的尾结点就位于，两个栈的栈顶，接下来比较两个栈的栈顶的节点是否相同；
     * 如果相同，则把栈顶元素弹出接着比较下一个栈顶，直到找到最后一个相同的节点；——两个链表的长度分别为m、 n——时间复杂度O(m + n)
     */

    public Node findFirstCommmonNode1(Node headA,Node headB){
        if(headA == null && headB == null){
            return null;
        }
        int lenA = 0;
        int lenB = 0;
        Node pl = headA;//pl永远指向最长的链表
        Node ps = headB;//ps永远指向最短的链表
        //(1)求得两链表的长度
        while(pl != null){
            pl = pl.next;
            lenA ++;
        }
        while(ps != null){
            ps = ps.next;
            lenB ++;
        }
        //将pl和ps指向头结点
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        //使得LenA总是指向最长的链表
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //代码走到此处：pl是指向最长的链表，ps指向最短的额链表
        //(2)让长的链表先走lenA - lenB步
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //(3)两个链表同时走，找第一个公共节点
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        return  pl;
    }

    public Node findFirstCommmonNode2(Node headA,Node headB){
        return null;
    }

    /***
     * 15.判断链表中是否有环:定义fast每一次走两步，slow每一次走一步，判断是否有环
     *
     *定义fast = fast.next.next;
     * 定义slow = slow.next;
     * @return
     */
    public boolean hasCycle1(){
        if(head == null){
            return false;
        }
        Node fast = this.head;
        Node slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return  false;
    }

    public boolean hasCycle2(){
        if(head == null){
            return false;
        }
        Node fast = this.head;
        Node slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //此处有两种情况：（1）遇到break循环退出；（2）循环条件不满足退出；
        if(fast == null || fast.next == null){
            return false;
        }
        return  true;
    }

    /***
     * 16.给定一个链表，返回链表开始入环的第一个节点，如果链表无环，则返回null；
     * 定义起始点到入环口的距离里是a;
     *    入环口到相遇点的距离是b;
     *    相遇点到入环口的距离是c；
     * 解法：(1)如果链表有环，那么快指针fast走过路程就是a+ b + c + b;
     *                      慢指针slow走过的路程就是a + b;
     *          在想通过的时间内，fast过的路程是慢指针的2倍；
     *          得出：a + b + c + b = 2(a + b) ——> a = c
     *
     *     （2）在相遇的时候，使用过两个指针，一个从链表的起始点开始，一个从相入口点开始；
     *         每次走一步，即fast走(b + c) == slow走(a + b)，直到再次相遇，即就是环的入口
     */
    public Node entryNodeOfLoop(){
        if(this.head == null){
            return  null;
        }
        //(1)定义快慢指针，判断链表是否有环
        Node fast = this.head;
        Node slow = this.head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //2种情况:循环条件不满足退出；遇到break退出
        if(fast == null || fast.next == null){
            return null;
        }
        //(2)定义两个指针，一个从链表的起始点开始，一个从环的入口点开始往后一步走；
        //定义slow从头结点开始一步往后走
        slow = this.head;
        while(fast != slow){
            fast = fast.next;
            slow= slow.next;
        }
        return fast;
    }

    /***
     * 17.删除中间节点
     *    删除单向链表中间的某个节点（既不是第一个或最后一节点），假定只能访问该节点
     *    输入：单向链表a b c d e f
     *    删除节点c
     *    输出：不返回任何数据，但该链表变为a b d e d
     *
     * @param node
     */
    public void deleteNode(Node node){
        if(node == null){
            return;
        }
        //未给定头结点，所以采用覆盖式进行删除；
        while(node != null){
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }

    /***
     * 18.右旋k步链表：
     * 给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中可是一个非负数
     * 输入：1 2 3 4 5 null ，k = 2;
     * 输出： 4 5 1 2 3 null
     *
     * 向右旋转1步：5 1 2 3 4 null
     * 向右旋转2步：4 5 1 2 3 null
     * @param k
     * @return
     */
    //方法1：使用快慢指针实现
    public Node rotateRightLinkedList(int k){
        if(this.head == null|| k < 0){
            return head;
        }
        if(head.next == null){
            return head;
        }
        if(k == 0){
            return head;
        }
        Node fast = this.head;
        Node slow = this.head;
        while(k != 0){
            //当k 值过大，可能出现空指针异常
            if(fast.next != null){
                fast = fast.next;
                k--;
            }else{
                fast = head;
                k--;
            }
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        //当k 等于链表 的长度的时候，直接返回表头head
        if(slow == head){
            return head;
        }
        Node tmp = slow.next;
        slow.next = null;
        fast.next = head;
        head = tmp;
        return head;
    }

    /**
     * 方法2：
     * @param k
     * @return
     */
    public Node rotateRightLinkedList2(int k) {

        if (head == null || head.next == null)
            return head;
        int count = 1;
        Node cur = head;
        while (cur.next != null) { //计算链表长度
            count++;
            cur = cur.next;
        }
        k = k % count;
        if (k == 0)
            return head;
        cur.next = head; // 将尾结点指向头结点
        Node node = new Node(-1);
        node.next = head;
        Node pre = node;
        for (int i = 0; i < count - k; i++) {
            pre = pre.next;
        }
        cur = pre.next;
        pre.next = null;
        return cur;
    }

}
